#
# @lc app=leetcode.cn id=204 lang=python3
#
# [204] 计数质数
#

# @lc code=start
class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2: return 0
        isPrime = [1] * n
        isPrime[0] = isPrime[1] = 0
        for i in range(2, int(n ** 0.5) + 1):
            if isPrime[i]:
                # ?n??????????
                isPrime[i * i: n: i] = [0] * len(isPrime[i * i: n: i])
        return sum(isPrime)



